Many data systems use clones. Clones can be used for variety of purposes including virtual machine boot image cloning, data recovery, data mining, backup, and testing. A clone is a point-in-time copy of a base data storage object. A storage object is a logical collection of data and is typically divided into logical blocks. In some systems clones can also be updated. That is, the clones are writeable. A desirable property of clones is space-efficiency. That is, a clone and its base can “share” data of the storage object that has not changed since the clone was created.
In a system having multiple clones, where each clone can be cloned, keeping track of the data stored and shared by each clone can become complicated. Some systems use b-trees to keep track of the data stored by a system's clones. A b-tree stores mappings between a logical address space and a physical address space. For example, a b-tree mapping can map a logical block of a file to a physical storage location of a physical volume. By accessing a b-tree, a user can determine the physical location of the logical blocks of a clone's storage object.